#include <stdio.h>
#include <stdlib.h>

// 二叉树节点结构
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 栈结构
typedef struct Stack {
    TreeNode** items;
    int top;
    int capacity;
} Stack;

// 创建新节点
TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 初始化栈
Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->items = (TreeNode**)malloc(sizeof(TreeNode*) * capacity);
    return stack;
}

// 检查栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == -1;
}

// 入栈操作
void push(Stack* stack, TreeNode* node) {
    if (stack->top == stack->capacity - 1) {
        printf("栈已满！\n");
        return;
    }
    stack->items[++stack->top] = node;
}

// 出栈操作
TreeNode* pop(Stack* stack) {
    if (isEmpty(stack)) {
        return NULL;
    }
    return stack->items[stack->top--];
}

// 获取栈顶元素
TreeNode* peek(Stack* stack) {
    if (isEmpty(stack)) {
        return NULL;
    }
    return stack->items[stack->top];
}

// 非递归中序遍历
void nonRecursiveInorder(TreeNode* root) {
    if (root == NULL) return;

    Stack* stack = createStack(100);
    TreeNode* current = root;

    printf("非递归中序遍历结果: ");

    while (current != NULL || !isEmpty(stack)) {
        // 遍历到最左边的节点
        while (current != NULL) {
            push(stack, current);
            current = current->left;
        }

        // 弹出栈顶节点并访问
        current = pop(stack);
        printf("%d ", current->data);

        // 转向右子树
        current = current->right;
    }
    printf("\n");

    free(stack->items);
    free(stack);
}

// 插入节点到二叉搜索树
TreeNode* insert(TreeNode* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }

    if (data < root->data) {
        root->left = insert(root->left, data);
    } else {
        root->right = insert(root->right, data);
    }
    return root;
}

// 主函数
int main() {
    TreeNode* root = NULL;
    int n, data;

    printf("请输入节点个数: ");
    scanf("%d", &n);

    printf("请输入%d个整数: ", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &data);
        root = insert(root, data);
    }

    nonRecursiveInorder(root);

    return 0;
}